#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int left=max(1,j-1);
                int right=min(n,j+1);
                dp[i][j]=min(dp[i-1][left],min(dp[i-1][right],dp[i-1][j]))+matrix[i-1][j-1];
            }
        }
        return *min_element(dp[m].begin()+1,dp[m].end());
    }
};

int main()
{
    vector<vector<int>> vec={{2,1,3},{6,5,4},{7,8,9}};
    Solution so;
    so.minFallingPathSum(vec);
    return 0;
}